package com.ddshuai.easy;

import java.util.Stack;

/**
 * 描述 新通教育
 *
 * @author ddshuai
 * @date 2018-09-27 下午4:57
 *
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
 *
 * 输入为非空字符串且只包含数字 1 和 0。
 *
 * 输入: a = "11", b = "1"
 * 输出: "100"
 *
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 **/
public class AddBinary {

    /**
     * 性别低下
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a,String b){
        Stack<String> result = new Stack<>();
        Integer needAddZeroCount = Math.abs(a.length()-b.length());
        String zeroStr = "";
        for (Integer i = 0; i < needAddZeroCount; i++) {
            zeroStr += "0";
        }
        if (a.length() < b.length()){
            a = zeroStr + a;
        }else {
            b = zeroStr + b;
        }

        char[] array = a.toCharArray();
        char[] array1 = b.toCharArray();
        boolean needStep = false;
        for (int i = array.length; i > 0; i-- ) {
            String a1 = String.valueOf(array[i-1]);
            String b1 = String.valueOf(array1[i-1]);
            Integer sum = Integer.parseInt(a1)+Integer.parseInt(b1);
            if (sum == 2){
                if (needStep){
                    result.add("1");
                }else {
                    result.add("0");
                }
                needStep = true;
            }else if (sum == 1){
                if (needStep){
                    result.add("0");
                    needStep = true;
                }else {
                    result.add("1");
                    needStep = false;
                }

            }else {
                if (needStep){
                    result.add("1");
                }else {
                    result.add("0");
                }
                needStep = false;
            }
        }
        if (needStep){
            result.add("1");
        }
        String res = "";
        while (!result.empty()){
            res += result.pop();
        }
        return res;
    }

    public static String addBinary1(String a,String b){
        String result = "";
        Integer needAddZeroCount = Math.abs(a.length()-b.length());
        String zeroStr = "";
        for (Integer i = 0; i < needAddZeroCount; i++) {
            zeroStr += "0";
        }
        if (a.length() < b.length()){
            a = zeroStr + a;
        }else {
            b = zeroStr + b;
        }

        char[] array = a.toCharArray();
        char[] array1 = b.toCharArray();
        boolean needStep = false;

        for (int i = array.length; i > 0; i-- ) {
            Character a1 = array[i-1];
            Character b1 = array1[i-1];
            int c1 = a1+b1;
            if (needStep){
                if (c1 == 98){
                    result = "1"+result;

                    needStep = true;
                }else if (c1 == 97){
                    result = "0"+result;
                    needStep = true;
                }else {
                    result = "1"+result;
                    needStep = false;
                }
            }else {
                if (c1 == 98){
                    result = "0"+result;
                    needStep = true;
                }else if (c1 == 97){
                    result = "1"+result;
                }else {
                    result = "0"+result;
                }
            }
        }
        if (needStep){
            result = "1"+result;
        }

        return result;
    }

    /**
     * 性能最高的  别人的解法
     * @param a
     * @param b
     * @return
     */
    public  static String addBinary2(String a,String b){
        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        if(aArray.length>=bArray.length){
            return addBinary(aArray,bArray);
        }
        return addBinary(bArray,aArray);
    }

    public static String addBinary(char[] aArray,char[] bArray){
        int target = 0;
        int initIndex = aArray.length-bArray.length;
        for(int i = bArray.length-1;i>=0;i--){
            int temp = (int)aArray[initIndex+i]+(int)bArray[i]+ target - (int)'0';
            if(temp>'1'){
                aArray[initIndex+i] = (char)(temp - 2);
                target = 1;
            }else {
                aArray[initIndex+i] = (char)temp;
                target = 0;
            }
        }
        if(target == 0){
            return String.valueOf(aArray);
        }
        for(int i = initIndex - 1;i>=0;i--){
            if(aArray[i]=='0'){
                aArray[i]++;
                return String.valueOf(aArray);
            }
            aArray[i]--;
        }
        return "1"+String.valueOf(aArray);
    }
    public static void main(String[] args) {
       System.out.println(addBinary2("1010","1011"));
    }
}
